package 双指针或滑动窗口.几乎唯一子数组的最大和2841;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        Integer[] a = new Integer[nums.size()];
        a = nums.toArray(a);
        long ans = 0, s = 0; // ans记录最大和，s记录当前窗口和
        Map<Integer, Integer> cnt = new HashMap<>(); // 元素出现次数计数器

        for (int i = 0; i < a.length; i++) { // 滑动窗口右边界i遍历数组
            // 1.【元素入窗】将a[i]加入窗口
            s += a[i];
            cnt.merge(a[i], 1, Integer::sum);

            // 2.【窗口成型判断】仅当窗口大小>=k时处理
            int left = i - k + 1; // 窗口左边界
            if (left < 0) continue; // 窗口未填满则跳过后续步骤

            // 3.【判断条件】哈希表大小即不同元素数量
            if (cnt.size() >= m)
                ans = Math.max(ans, s); // 更新最大和

            // 4.【元素出窗】窗口滑动前移除最左元素
            int out = a[left];
            s -= out; // 减去出窗元素的和
            // 更新哈希表计数
            int c = cnt.get(out);
            if (c > 1) cnt.put(out, c - 1);
            else cnt.remove(out); // 计数归零时移除键
        }
        return ans;
    }
}
